import UIKit

//LeetCode 刷题

print("************* 2、数组 *************");
print("【704】二分查找 难度：简单");

/**
 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

//target在[left, right]区间
func binarySearch(nums: [Int], target: Int) -> Int {
    var left = 0;
    var right = nums.count - 1;
    while (left <= right) {
        let mid = left + (right - left) / 2;
        if (nums[mid] == target){
            return mid;
        } else if (nums[mid] < target){
            left = mid + 1;
        } else if (nums[mid] > target){
            right = mid - 1;
        }
    }
    return -1
}
 
//target在[left, right)区间
func binarySearch2(nums: [Int], target: Int) -> Int {
    var left = 0;
    var right = nums.count;
    while (left < right) {
        let mid = left + (right - left) / 2;
        if (nums[mid] == target){
            return mid;
        } else if (nums[mid] < target){
            left = mid + 1;
        } else if (nums[mid] > target){
            right = mid;
        }
    }
    return -1
}

binarySearch2(nums: [-1,0,3,5,9,12], target: 9);
*/

print("【27】移除元素 难度：简单");

/**
 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

func removeElement(nums: inout [Int], val: Int) -> Int {
    var slowIndex = 0
    for fastIndex in 0..<nums.count {
        if val != nums[fastIndex] {
            if slowIndex != fastIndex {
                nums[slowIndex] = nums[fastIndex]
            }
            slowIndex += 1
        }
    }
    return slowIndex
}

var nums = [3,2,2,3]
removeElement(nums:&nums, val: 3)
 */

print("【977】有序数组的平方 难度：简单");
/**
 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
 示例 1：

 输入：nums = [-4,-1,0,3,10]
 输出：[0,1,9,16,100]
 解释：平方后，数组变为 [16,1,0,9,100]
 排序后，数组变为 [0,1,9,16,100]

 链接：https://leetcode.cn/problems/squares-of-a-sorted-array
func sortedSquares(_ nums: [Int]) -> [Int] {
    // 指向新数组最后一个元素
    var k = nums.count - 1
    // 指向原数组第一个元素
    var i = 0
    // 指向原数组最后一个元素
    var j = nums.count - 1
    // 初始化新数组(用-1填充)
    var result = Array<Int>(repeating: -1, count: nums.count)

    for _ in 0..<nums.count {
        if nums[i] * nums[i] < nums[j] * nums[j] {
            result[k] = nums[j] * nums[j]
            j -= 1
        } else {
            result[k] = nums[i] * nums[i]
            i += 1
        }
        k -= 1
    }

    return result
}

sortedSquares([-4,-1,0,3,10]);
 */

print("【209】长度最小的子数组 难度：中等");
/**
 给定一个含有 n 个正整数的数组和一个正整数 target 。

 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

 示例 1：

 输入：target = 7, nums = [2,3,1,2,4,3]
 输出：2
 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

 来源：力扣（LeetCode）
 链接：https://leetcode.cn/problems/minimum-size-subarray-sum
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 

func minSubArrayLen(_ target: Int, _ nums: [Int]) -> Int {
    var result = Int.max
    var sum = 0
    var starIndex = 0
    for endIndex in 0..<nums.count {
        sum += nums[endIndex]

        while sum >= target {
            result = min(result, endIndex - starIndex + 1)
            sum -= nums[starIndex]
            starIndex += 1
        }
    }

    return result == Int.max ? 0 : result
}

minSubArrayLen(7, [2,3,1,2,4,3])
 */

print("【509】螺旋矩阵 II 难度：中等");
/**
 给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
 输入：n = 3
 输出：[[1,2,3],[8,9,4],[7,6,5]]


func generateMatrix(_ n: Int) -> [[Int]] {
    var result = [[Int]](repeating: [Int](repeating: 0, count: n), count: n)

    var startRow = 0
    var startColumn = 0
    var loopCount = n / 2
    let mid = n / 2
    var count = 1
    var offset = 1
    var row: Int
    var column: Int

    while loopCount > 0 {
        row = startRow
        column = startColumn

        for c in column ..< startColumn + n - offset {
            result[startRow][c] = count
            count += 1
            column += 1
        }

        for r in row ..< startRow + n - offset {
            result[r][column] = count
            count += 1
            row += 1
        }

        for _ in startColumn ..< column {
            result[row][column] = count
            count += 1
            column -= 1
        }

        for _ in startRow ..< row {
            result[row][column] = count
            count += 1
            row -= 1
        }

        startRow += 1
        startColumn += 1
        offset += 2
        loopCount -= 1
    }

    if (n % 2) != 0 {
        result[mid][mid] = count
    }
    return result
}

generateMatrix(3)
 */

print("************* 2、链表 *************");

var list = ListNode(6,ListNode(5,ListNode(4, ListNode(3, ListNode(6, ListNode(2, ListNode(1)))))));

print("【203】移除链表元素 难度：简单");
/**
 给你一个链表的头节点 head 和一个整数 val ，
 请你删除链表中所有满足 Node.val == val 的节点，
 并返回 新的头节点 。
 
 输入：head = [1,2,6,3,4,5,6], val = 6
 输出：[1,2,3,4,5]

func removeElements(_ head: ListNode?, _ val: Int) -> ListNode? {
    let dummyNode = ListNode()
    dummyNode.next = head
    var currentNode = dummyNode
    while let curNext = currentNode.next {
        if curNext.val == val {
            currentNode.next = curNext.next
        } else {
            currentNode = curNext
        }
    }
    return dummyNode.next
}

removeElements(list,6);
*/

print("【707】设计链表 难度：中等");
/**
 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

 在链表类中实现这些功能：

 get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
 addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
 addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
 addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
 deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

 来源：力扣（LeetCode）
 链接：https://leetcode.cn/problems/design-linked-list
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 
class MyLinkedList {

    var dummyHead: ListNode?
    var size: Int
    
    init() {
        dummyHead = ListNode(0)
        size = 0
    }
    
    func get(_ index: Int) -> Int {
        if index >= size || index < 0 {
            return -1
        }
        
        var curNode = dummyHead?.next
        var curIndex = index
        
        while curIndex > 0 {
            curNode = curNode?.next
            curIndex -= 1
        }
        
        return curNode?.val ?? -1
    }
    
    func addAtHead(_ val: Int) {
        let newHead = ListNode(val)
        newHead.next = dummyHead?.next
        dummyHead?.next = newHead
        size += 1
    }
    
    func addAtTail(_ val: Int) {
        let newNode = ListNode(val)
        var curNode = dummyHead
        while curNode?.next != nil {
            curNode = curNode?.next
        }
        
        curNode?.next = newNode
        size += 1
    }
    
    func addAtIndex(_ index: Int, _ val: Int) {
        if index > size {
            return
        }
        
        let newNode = ListNode(val)
        var curNode = dummyHead
        var curIndex = index
      
        while curIndex > 0 {
            curNode = curNode?.next
            curIndex -= 1
        }
      
        newNode.next = curNode?.next
        curNode?.next = newNode
        size += 1
    }
    
    func deleteAtIndex(_ index: Int) {
        if index >= size || index < 0 {
            return
        }
        
        var curNode = dummyHead
        for _ in 0..<index {
            curNode = curNode?.next
        }
        
        curNode?.next = curNode?.next?.next
        size -= 1
    }
}

let obj = MyLinkedList()
let ret_1: Int = obj.get(0)
obj.addAtHead(1)
obj.addAtTail(2)
obj.addAtIndex(1, 3)
obj.deleteAtIndex(2)
 */

print("【206】反转链表 难度：简单");
/**
 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 输入：head = [1,2,3,4,5]
 输出：[5,4,3,2,1]

/// 双指针法 (迭代)
/// - Parameter head: 头结点
/// - Returns: 翻转后的链表头结点
func reverseList(_ head: ListNode?) -> ListNode? {
    if head == nil || head?.next == nil {
        return head
    }
    var pre: ListNode? = nil
    var cur: ListNode? = head
    var temp: ListNode? = nil
    while cur != nil {
        temp = cur?.next
        cur?.next = pre
        pre = cur
        cur = temp
    }
    return pre
}

/// 递归
/// - Parameter head: 头结点
/// - Returns: 翻转后的链表头结点
func reverseList2(_ head: ListNode?) -> ListNode? {
    return reverse(pre: nil, cur: head)
}
func reverse(pre: ListNode?, cur: ListNode?) -> ListNode? {
    if cur == nil {
        return pre
    }
    let temp: ListNode? = cur?.next
    cur?.next = pre
    return reverse(pre: cur, cur: temp)
}

reverseList2(list)
*/

print("【24】两两交换链表中的节点 难度：中等");
/**
 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
 输入：head = [1,2,3,4]
 输出：[2,1,4,3]
 https://leetcode.cn/problems/swap-nodes-in-pairs/
 
func swapPairs(_ head: ListNode?) -> ListNode? {
    if head == nil || head?.next == nil {
        return head
    }
    let dummyHead: ListNode = ListNode(-1, head)
    var current: ListNode? = dummyHead
    while current?.next != nil && current?.next?.next != nil {
        let temp1 = current?.next
        let temp2 = current?.next?.next?.next
        
        current?.next = current?.next?.next
        current?.next?.next = temp1
        current?.next?.next?.next = temp2
        
        current = current?.next?.next
    }
    return dummyHead.next
}

swapPairs(list)
 */

print("【19】删除链表的倒数第 N 个结点 难度：中等");
/**
 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 输入：head = [1,2,3,4,5], n = 2
 输出：[1,2,3,5]
 https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
 
func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
    if head == nil {
        return nil
    }
    if n == 0 {
        return head
    }
    let dummyHead = ListNode(-1, head)
    var fast: ListNode? = dummyHead
    var slow: ListNode? = dummyHead
    // fast 前移 n
    for _ in 0 ..< n {
        fast = fast?.next
    }
    while fast?.next != nil {
        fast = fast?.next
        slow = slow?.next
    }
    slow?.next = slow?.next?.next
    return dummyHead.next
}

removeNthFromEnd(list,2)
 */

print("【160】相交链表 难度：简单");
/**
 listA = [0,4,1,8,4,5], listB = [5,0,1,8,4,5]
 Intersected at '8'
 https://leetcode.cn/problems/intersection-of-two-linked-lists/
 
 【双指针】
 这里需要的是数学证明了，因为首尾相接，所以他们每一次轮回的路程相等，既 A+B=B+A。

 不管 相不相交， 当 currentA拼接B的时候，currentB拼接A的时候，他们能同时走到对方的尾节点，如果不相交，此时都为空，跳出循环
 如果相交，那么我们逆推，既然能在尾节点相遇，那么尾节点的前继节点也是相遇，直到我们逆推到第一个相交点。

func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {
  var currentA = headA
  var currentB = headB
  //！ 等价于 同一对象
  while currentA !== currentB {
    currentA = (currentA != nil) ? currentA?.next : headB
    currentB = (currentB != nil) ? currentB?.next : headA
  }
  return currentA
}

//哈希表
func getIntersectionNode2(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {
  var hashSet = Set<ListNode>()

  var current = headA
  while current != nil {
    hashSet.insert(current!)
    current = current!.next
  }

  current = headB

  while current != nil {
  
    if hashSet.contains(current!) {
      break
    }
    current = current?.next
  }
     
   return current
}

extension ListNode: Hashable, Equatable {
    public func hash(into hasher: inout Hasher) {
        // 用于唯一标识
        hasher.combine(val)
        hasher.combine(ObjectIdentifier(self))
    }

    public static func ==(lhs: ListNode, rhs: ListNode) -> Bool {
        return lhs === rhs
    }
 }

var listNode8 = ListNode(8, ListNode(4, ListNode(5)));
var list1 = ListNode(0,ListNode(4,ListNode(1, listNode8)));
var list2 = ListNode(5,ListNode(0, ListNode(1, listNode8)));
getIntersectionNode(list1,list2)
 */

print("【142】环形链表 II 难度：中等");
/**
 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

 不允许修改 链表。

 链接：https://leetcode.cn/problems/linked-list-cycle-ii

func detectCycle(_ head: ListNode?) -> ListNode? {
    var slow: ListNode? = head
    var fast: ListNode? = head
    while fast != nil && fast?.next != nil {
        slow = slow?.next
        fast = fast?.next?.next
        if slow == fast {
            // 环内相遇
            var list1: ListNode? = slow
            var list2: ListNode? = head
            while list1 != list2 {
                list1 = list1?.next
                list2 = list2?.next
            }
            return list2
        }
    }
    return nil
}

extension ListNode: Equatable {
    public func hash(into hasher: inout Hasher) {
        hasher.combine(val)
        hasher.combine(ObjectIdentifier(self))
    }
    public static func == (lhs: ListNode, rhs: ListNode) -> Bool {
        return lhs === rhs
    }
}
*/

print("************* 3、哈希表 *************");

print("【242】有效的字母异位词 难度：简单");
/*
 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

 注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

 示例 1:

 输入: s = "anagram", t = "nagaram"
 输出: true
 
 链接：https://leetcode.cn/problems/valid-anagram
 
func isAnagram(_ s: String, _ t: String) -> Bool {
    if s.count != t.count {
        return false
    }
    var record = Array(repeating: 0, count: 26)
    let aUnicodeScalar = "a".unicodeScalars.first!.value
    for c in s.unicodeScalars {
        record[Int(c.value - aUnicodeScalar)] += 1
    }
    for c in t.unicodeScalars {
        record[Int(c.value - aUnicodeScalar)] -= 1
    }
    for value in record {
        if value != 0 {
            return false
        }
    }
    return true
}

var s = "anagram", t = "nagaram"

isAnagram(s,t)
 */

print("【349】两个数组的交集 难度：简单");
/**
 给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
 示例 1：

 输入：nums1 = [1,2,2,1], nums2 = [2,2]
 输出：[2]

 func intersection(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
     var set1 = Set<Int>()
     var set2 = Set<Int>()
     for num in nums1 {
         set1.insert(num)
     }
     for num in nums2 {
         if set1.contains(num) {
             set2.insert(num)
         }
     }
     return Array(set2)
 }
 */

print("【202】快乐数 难度：简单");
/**
 编写一个算法来判断一个数 n 是不是快乐数。

 「快乐数」 定义为：

 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
 如果这个过程 结果为 1，那么这个数就是快乐数。
 如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

 示例 1：

 输入：n = 19
 输出：true
 解释：
 12 + 92 = 82
 82 + 22 = 68
 62 + 82 = 100
 12 + 02 + 02 = 1

 来源：力扣（LeetCode）
 链接：https://leetcode.cn/problems/happy-number
 
 func getSum(_ number: Int) -> Int {
     var sum = 0
     var num = number
     while num > 0 {
         let temp = num % 10
         sum += (temp * temp)
         num /= 10
     }
     return sum
 }
 func isHappy(_ n: Int) -> Bool {
     var set = Set<Int>()
     var num = n
     while true {
         let sum = self.getSum(num)
         if sum == 1 {
             return true
         }
         // 如果这个sum曾经出现过，说明已经陷入了无限循环了
         if set.contains(sum) {
             return false
         } else {
             set.insert(sum)
         }
         num = sum
     }
 }
 */

print("【1】两数之和 难度：简单");
/**
 输入：nums = [2,7,11,15], target = 9
 输出：[0,1]
 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    //1、初始化哈希表
    var table:[Int:Int] = [Int:Int]()
    //2、遍历下标和元素
    for (index,num) in nums.enumerated() {
        //3、获取目标值减元素的差值
        let value:Int = target - num
        //4、如果差值在哈希表中找到，返回下标元素
        if let resIndex = table[value]
        {
            return [resIndex,index]
        }
        //5、哈希表存储元素值和下标
        else
        {
            table[num] = index;
        }
    }
    //6、找不到，返回
    return [-1,-1]
}

twoSum([2,7,11,15], 9)
*/

print("【454】四数相加 II 难度：中等");
/**
 给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

 0 <= i, j, k, l < n
 nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
  
 示例 1：

 输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
 输出：2
 解释：
 两个元组如下：
 1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
 2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

 来源：力扣（LeetCode）
 链接：https://leetcode.cn/problems/4sum-ii
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 
 func fourSumCount(_ nums1: [Int], _ nums2: [Int], _ nums3: [Int], _ nums4: [Int]) -> Int {
     // ab和: ab和出现次数
     var countDic = [Int: Int]()
     for a in nums1 {
         for b in nums2 {
             let key = a + b
             countDic[key] = countDic[key, default: 0] + 1
         }
     }

     // 通过-(c + d)作为key，去累加ab和出现的次数
     var result = 0
     for c in nums3 {
         for d in nums4 {
             let key = -(c + d)
             result += countDic[key, default: 0]
         }
     }
     return result
 }
 */

print("【383】赎金信 难度：简单");
/**
 给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

 如果可以，返回 true ；否则返回 false 。

 magazine 中的每个字符只能在 ransomNote 中使用一次。

 示例 1：
 输入：ransomNote = "a", magazine = "b"
 输出：false

 来源：力扣（LeetCode）
 链接：https://leetcode.cn/problems/ransom-note
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 
func canConstruct(_ ransomNote: String, _ magazine: String) -> Bool {
    var record = Array(repeating: 0, count: 26);
    let aUnicodeScalarValue = "a".unicodeScalars.first!.value
    for unicodeScalar in magazine.unicodeScalars {
        // 通过record 记录 magazine 里各个字符出现的次数
        let idx: Int = Int(unicodeScalar.value - aUnicodeScalarValue)
        record[idx] += 1
    }
    for unicodeScalar in ransomNote.unicodeScalars {
        // 遍历 ransomNote,在record里对应的字符个数做 -- 操作
        let idx: Int = Int(unicodeScalar.value - aUnicodeScalarValue)
        record[idx] -= 1
        // 如果小于零说明在magazine没有
        if record[idx] < 0 {
            return false
        }
    }
    return true
}
 */

print("【15】三数之和 难度：中等");
/**
 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

 你返回所有和为 0 且不重复的三元组。

 注意：答案中不可以包含重复的三元组。

 示例 1：

 输入：nums = [-1,0,1,2,-1,-4]
 输出：[[-1,-1,2],[-1,0,1]]
 解释：
 nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
 注意，输出的顺序和三元组的顺序并不重要。

 来源：力扣（LeetCode）
 链接：https://leetcode.cn/problems/3sum
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 
 func threeSum(_ nums: [Int]) -> [[Int]] {
     var res = [[Int]]()
     var sorted = nums
     sorted.sort()
     for i in 0 ..< sorted.count {
         if sorted[i] > 0 {
             return res
         }
         if i > 0 && sorted[i] == sorted[i - 1] {
             continue
         }
         var left = i + 1
         var right = sorted.count - 1
         while left < right {
             let sum = sorted[i] + sorted[left] + sorted[right]
             if sum < 0 {
                 left += 1
             } else if sum > 0 {
                 right -= 1
             } else {
                 res.append([sorted[i], sorted[left], sorted[right]])
                 
                 while left < right && sorted[left] == sorted[left + 1] {
                     left += 1
                 }
                 while left < right && sorted[right] == sorted[right - 1] {
                     right -= 1
                 }
                 
                 left += 1
                 right -= 1
             }
         }
     }
     return res
 }
 */

print("【18】四数之和 难度：中等");
/**
 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

 0 <= a, b, c, d < n
 a、b、c 和 d 互不相同
 nums[a] + nums[b] + nums[c] + nums[d] == target
 你可以按 任意顺序 返回答案 。

 示例 1：

 输入：nums = [1,0,-1,0,-2,2], target = 0
 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

 来源：力扣（LeetCode）
 链接：https://leetcode.cn/problems/4sum
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 
 func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
     var res = [[Int]]()
     var sorted = nums
     sorted.sort()
     for k in 0 ..< sorted.count {
         // 这种剪枝不行,target可能是负数
 //            if sorted[k] > target {
 //                return res
 //            }
         // 去重
         if k > 0 && sorted[k] == sorted[k - 1] {
             continue
         }
         
         let target2 = target - sorted[k]
         for i in (k + 1) ..< sorted.count {
             if i > (k + 1) && sorted[i] == sorted[i - 1] {
                 continue
             }
             var left = i + 1
             var right = sorted.count - 1
             while left < right {
                 let sum = sorted[i] + sorted[left] + sorted[right]
                 if sum < target2 {
                     left += 1
                 } else if sum > target2 {
                     right -= 1
                 } else {
                     res.append([sorted[k], sorted[i], sorted[left], sorted[right]])
                     while left < right && sorted[left] == sorted[left + 1] {
                         left += 1
                     }
                     while left < right && sorted[right] == sorted[right - 1]  {
                         right -= 1
                     }
                     // 找到答案 双指针同时收缩
                     left += 1
                     right -= 1
                 }
             }
         }
     }
     return res
 }
 */

//【2】两数相加 难度：中等
/**
 输入：l1 = [2,4,3], l2 = [5,6,4]
 输出：[7,0,8]
 解释：342 + 465 = 807.

func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    //如果l1和l2为空，返回nil
    guard let l1 = l1,let l2 = l2 else {return nil}
    //计算两链表值的和
    var sum = l1.val + l2.val
    //值模10
    let newNode = ListNode(sum%10)
    var theNode:ListNode? = newNode
    //值大于10，进位
    var addOne = sum >= 10 ? 1 : 0
    var node1:ListNode? = l1.next
    var node2:ListNode? = l2.next
    while node1 != nil || node2 != nil {
        sum = (node1?.val ?? 0) + (node2?.val ?? 0)
        theNode?.next = ListNode((sum+addOne)%10)
        if sum+addOne >= 10{
            addOne = 1
        }else{
            addOne = 0
        }
        if node1?.next != nil || node2?.next != nil{
            node1 = node1?.next != nil ? node1?.next : ListNode(0)
            node2 = node2?.next != nil ? node2?.next : ListNode(0)
        }else{
            node1 = nil
            node2 = nil
        }
        theNode = theNode?.next
    }
    if addOne > 0{
        theNode?.next = ListNode(addOne)
    }
    return newNode
}

var l2 = ListNode(2)
var l4 = ListNode(4)
var l3 = ListNode(3)
l2.next = l4;
l4.next = l3;

var l5 = ListNode(5)
var l6 = ListNode(6)
l5.next = l6;
l6.next = ListNode(4);

addTwoNumbers(l2,l5)
*/

//【5】最长回文子串 难度：中等
func longestPalindrome(_ s: String) -> String {
    return ""
}

//在s中寻找以s[l]和s[r]为中心的最长回文串
//func palindrome(String s,int l,int r) -> String {
//
//}

//【26】删除有序数组中的重复项 难度：简单
/*
func removeDuplicates(_ nums: inout [Int]) -> Int {
    if nums.isEmpty {
        return 0;
    }
    var slow = 0,fast = 0
    while (fast < nums.count){
        if nums[fast] != nums[slow] {
            slow += 1;
            //维护 nums[0..slow]无重复
            nums[slow] = nums[fast]
        }
        fast += 1;
    }
    //数组长度为索引 + 1
    return slow + 1;
}

var nums = [0,0,1,1,1,2,2,3,3,4]
removeDuplicates(&nums)
*/

//【283】移动零 难度：简单
/*
func moveZeroes(nums: inout [Int]) {
    //去除nums中的所有0
    //但会去除0之后的数组长度
    let p = removeElement(nums: &nums, val: 0);
    //将 P 之后的所有元素赋值为0
    for (index,_) in nums.enumerated(){
        if index >= p {
            nums[index] = 0
        }
    }
}

func removeElement(nums: inout [Int], val: Int) -> Int {
    var slowIndex = 0
    for fastIndex in 0..<nums.count {
        if val != nums[fastIndex] {
            if slowIndex != fastIndex {
                nums[slowIndex] = nums[fastIndex]
            }
            slowIndex += 1
        }
    }
    return slowIndex
}

var nums = [0,1,0,3,12]
moveZeroes(nums: &nums);
*/

//【344】反转字符串 难度：简单
/*
func reverseString(s: inout [String]) {
    //一左一右两个指针相向而行
    var left = 0,right = s.count - 1;
    while (left < right){
        let temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        left += 1;
        right -= 1;
    }
}

var s = ["h","e","l","l","o"];
reverseString(s: &s);
*/



